public class No033 {
    /**
     * 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。
     * 如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
     */
    public static boolean VerifySequenceOfBST(int[] sequence) {
        if (sequence.length == 0) return false;
        return Verify(sequence, 0, sequence.length);
    }

    public static boolean Verify(int[] sequence, int left, int right) {
        if (right == left) return true;
        int root = sequence[right - 1];
        int i = 0;
        for (; i < right - 1; i++) {
            if (sequence[i] > root) break;
        }
        for (int j = i; j < right - 1; j++) {
            if (sequence[j] < root) return false;
        }
        return Verify(sequence, left, i) && Verify(sequence, i, right - 1);
    }

    public static void main(String[] args) {
        int[] arr = {5, 9, 8};
        System.out.println(VerifySequenceOfBST(arr));
    }
}
